home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / graphics / tree / tree.l < prev    next >
Text File  |  1993-09-01  |  47KB  |  1,736 lines
  1. %{
  2. /* tree: format trees
  3.  * Version 1.1 -- Greg Lee, lee@uhccux.uhcc.hawaii.edu, June 24, 1990
  4.  *
  5.  * This program is free and in the public domain.  Please keep future
  6.  * versions in the public domain.
  7.  *
  8.  * The inspiration for and predecessor to `tree' was a program by
  9.  * Chris Barker, of the Linguistics Board at University of California,
  10.  * Santa Cruz, email: barker@ling.ucsc.edu.
  11.  *
  12.  * A pattern matching function yylex() is built, which finds tree
  13.  * definitions in a text;  yylex() is called recursively to build
  14.  * a tree structure in memory;  a sequence of formatting operations
  15.  * is carried out (see printtree()); then the formatted tree is
  16.  * displayed by tty() or, for TeX code, the function tex().
  17.  */
  18. #include <ctype.h>
  19.  
  20. #define TRUE 1
  21. #define FALSE 0
  22.  
  23. /* When formatting for TeX, multiply column widths by this to get better
  24.  * positioning:
  25.  */
  26. #define COLMUL 8
  27.  
  28. /* The c_ values are from the command line; the real values are taken
  29.  * from them or from options given after the \tree command.
  30.  */
  31.     int     tex_opt, c_tex_opt = FALSE;    /* generate TeX code? */
  32.     int     utex_opt, c_utex_opt = FALSE;/* generate TeX code with PS? */
  33.     int     gap_opt, c_gap_opt = 2;    /* space between subtrees */
  34.     int     black_opt, c_black_opt = 0;    /* black triangles */
  35.     int     debug_opt = FALSE;    /* tracing? */
  36.     int     quiet_opt, c_quiet_opt = FALSE;    /* no warnings */
  37.     int     verbose_opt, c_verbose_opt = FALSE; /* show tex commands? */
  38.     int     lexical_opt, c_lexical_opt = FALSE;  /* no lines */
  39.     int     T_opt, c_T_opt = FALSE;
  40.     int     O_opt, c_O_opt = FALSE;
  41.     int     I_opt, c_I_opt = FALSE;
  42.     int     F_opt, c_F_opt = FALSE;
  43.     int     E_opt, c_E_opt = FALSE;
  44.     int     R_opt, c_R_opt = FALSE;
  45.  
  46. /* count columns before \tree command encountered */
  47.     int     indent = 0;
  48. /* count caps in name to compensate for extra width */
  49.     int     capscount = 0;
  50. /* keep track of recursion in yylex() calls to assign nodes to rows */
  51.     int     level = 0;
  52.     int     maxlevel = 0;
  53. /* source line (not useful now -- need some error checking) */
  54.     int     linenumber = 1;
  55.  
  56. /* types of nodes */
  57. #define HBAR 1            /* horizontal bar */
  58. #define VBAR 2            /* vertical bar */
  59. #define OBAR 4            /* horizontal overbar */
  60. #define NODENAME 8        /* named node */
  61.  
  62. #define NAMEROOM 20000        /* how much to malloc for node names */
  63. char    *buf, *bufp;        /* for buffer storing node names */
  64.  
  65. /* A node has a:
  66.  *    row, from row 1, telling how far from the top of the tree it is;
  67.  *    col, from col 0, how far from the left;
  68.  *    mid, its horizontal mid point, used for vertical alignment;
  69.  *    l, its width in columns;
  70.  *    treeid, an identifying number;
  71.  *    type, whether its a name or a bar of some sort;
  72.  *    attrib, a list of 26 values of attributes bestowed by \<cap>s;
  73.  *    n, pointer to its name if it has one;
  74.  *    and a bunch of pointers to contiguous nodes in the tree.
  75.  *
  76.  * Attributes `S' and `U' are used internally;  must change this if
  77.  * there are to be \S or \U commands.
  78.  */
  79. typedef struct list {
  80.     int row, col, mid, l, treeid, type;
  81.     char attrib[26];
  82.     char *n;
  83.     struct list *daughter;
  84.     struct list *sister;
  85.     struct list *mother;
  86.     struct list *right;
  87.     struct list *left;
  88. } LIST, *TREE;
  89.  
  90. /* next number for treeid */
  91. int treenum = 1;
  92.  
  93. TREE newnode();
  94.  
  95. /* global reference by yylex() */
  96. TREE tree;
  97.  
  98. #define ERROR(message) fprintf(stderr,"Tree: %s (line %d).\n", \
  99.         message, linenumber)
  100.  
  101. /* Next is code for flex to build the yylex() function.  There are three
  102.  * states the pattern matcher can be in:
  103.  *    T, if it's matching text after the \tree command that defines
  104.  *        a tree;
  105.  *    N, if it's echoing text that is not in the scope of a \tree command;
  106.  *    C, if it's discarding comments within the definition of a tree.
  107.  */
  108. %}
  109.  
  110. %s T N C
  111.  
  112. %%
  113. <N>\n {
  114.     indent = 0;
  115.     linenumber++;
  116.     ECHO;
  117. }
  118. <N>\t {
  119.     indent++;
  120.     while (indent % 8) indent++;
  121.     ECHO;
  122. }
  123. <N>. {
  124.     indent++;
  125.     ECHO;
  126. }
  127. <N>\\tree[ \t\n]*(-([tuvqLTOIFER]+|[bg][0-9]+)[ \t\n]*)*\([ \t\n]* {
  128.     TREE root;
  129.  
  130.     setoptions(yytext + 5);
  131.     level++;
  132.     if (level > maxlevel) maxlevel = level;
  133.     root = newnode(level,bufp);
  134.     tree = root;
  135. /* do a whole tree: in state T analyze the tree definition
  136.  * and build the tree; format and display, and resume echoing
  137.  * text until the next tree definition is found.
  138.  */
  139.     BEGIN(T);
  140.     yylex();
  141.     printtree(root);
  142.     maxlevel = 0;
  143.     BEGIN(N);
  144. }
  145. <N>\\tree {
  146.     if (!quiet_opt) ERROR("ill-formed \\tree command ignored");
  147.     ECHO;
  148. }
  149. <T,C>\([ \t\n]* {
  150.     TREE node;
  151.  
  152.     notenewlines(yytext);
  153.     level++;
  154.     if (level > maxlevel) maxlevel = level;
  155.     addchar('\0');    /* terminate last node name */
  156.     capscount = 0;    /* no caps in next name yet */
  157.     node = newnode(level,bufp);
  158. /* nodes at same level of embedding are connected together as
  159.  * sisters; but if current level is greater than that of
  160.  * the node that was just being made, this next node must be
  161.  * a daughter of that node.
  162.  */
  163.     if (tree->row < level) tree->daughter = node;
  164.     else tree->sister = node;
  165.     tree = node;
  166.     BEGIN(T);
  167.     yylex();
  168.     tree = node;
  169. }
  170. <T,C>\) {
  171.     level--;
  172.     addchar('\0');
  173.     capscount = 0;
  174. /* discard text now until the beginning of the next node
  175.  */
  176.     BEGIN(C);
  177. /* this is a return from a yylex() invocation called from yylex().
  178.  */
  179.     return;
  180. }
  181. <T>[ \t\n]+\\% {
  182.     notenewlines(yytext);
  183.     addchar(' ');
  184.     if (tex_opt || verbose_opt) {
  185.         addchar('\\');
  186.         tree->l++;
  187.     }
  188.     addchar('%');
  189.     tree->l += 2;
  190. }
  191. <T>\\[%#\&\$] {
  192.     if (tex_opt || verbose_opt) {
  193.         addchar('\\');
  194.         tree->l++;
  195.     }
  196.     addchar(yytext[1]);
  197.     tree->l++;
  198. }
  199. <T,C>%.*\n {
  200.     notenewlines(yytext);
  201. }
  202. <T,C>[ \t\n]*%.*\n[ \t\n]*/[\)\(] {
  203.     notenewlines(yytext);
  204. }
  205. <T>\\[MDB][0-9][ \t\n]+ {
  206.     giveval(tree, yytext[1], yytext[2]);
  207. }
  208. <T>\\[MDB][0-9]/[^A-Za-z] {
  209.     giveval(tree, yytext[1], yytext[2]);
  210. }
  211. <T>\\[A-Z][ \t\n]+ {
  212.     give(tree, yytext[1]);
  213. }
  214. <T>\\[A-Z]/[^A-Za-z] {
  215.     give(tree, yytext[1]);
  216. }
  217. <T>\\[ )(\\] {
  218.     addchar(yytext[1]);
  219.     tree->l++;
  220. }
  221. <T>(\\[`'"^~=.])|(\$[_^]) {
  222.     if (tex_opt || verbose_opt) {
  223.         addchar(yytext[0]);
  224.         addchar(yytext[1]);
  225.         if (verbose_opt) tree->l += 2;
  226.     }
  227. }
  228. <T>[\${}] {
  229.     if (tex_opt || verbose_opt) {
  230.         addchar(yytext[0]);
  231.         if (verbose_opt) tree->l++;
  232.     }
  233. }
  234. <T>[A-HJ-Z] {
  235.     addchar(yytext[0]);
  236.     tree->l++;
  237.     if (tex_opt && ++capscount > 3) {
  238.         tree->l++;
  239.         capscount = 0;
  240.     }
  241. }
  242. <T>. {
  243.     addchar(yytext[0]);
  244.     tree->l++;
  245. }
  246. <T>\\tree[ \t\n]* {
  247.     if (!quiet_opt) ERROR("\\tree command found inside tree");
  248.     notenewlines(yytext);
  249.     if (tex_opt || verbose_opt) {
  250.         int i;
  251.         for (i = 0; i < yyleng; i++) {
  252.             addchar(yytext[i]);
  253.             if (verbose_opt) tree->l++;
  254.         }
  255.     }
  256. }
  257. <T>\\[A-Za-z]+[ \t\n]* {
  258.     notenewlines(yytext);
  259.     if (tex_opt || verbose_opt) {
  260.         int i;
  261.         for (i = 0; i < yyleng; i++) {
  262.             addchar(yytext[i]);
  263.             if (verbose_opt) tree->l++;
  264.         }
  265.     }
  266. }
  267.  
  268. <T>[ \t\n]+/[\)\(] {
  269.     notenewlines(yytext);
  270. }
  271. <T>[ \t\n]+ {
  272.     notenewlines(yytext);
  273.     if (tree->l) {    
  274.         addchar(' ');
  275.         tree->l++;
  276.     }
  277. }
  278. <C>[^ \t\n\(\)]+ {
  279.     if (!quiet_opt) ERROR("word after node name ignored");
  280. }
  281. <C>.    ;
  282. <C>\n    linenumber++;
  283.  
  284. %%
  285.  
  286. /* count newlines in string; update linecount; issue warning if
  287.  * blank line
  288.  */
  289. notenewlines(s)
  290. char *s;
  291. {    int warn = 0;
  292.     while (*s) {
  293.         if (*s == '\n') {
  294.             if (warn && !quiet_opt)
  295.                 ERROR("blank line within tree");
  296.             else warn++;
  297.             linenumber++;
  298.         }
  299.         else if (*s != ' ' && *s != '\t') warn = 0;
  300.         s++;
  301.     }
  302. }
  303.  
  304. /* Called for every \tree in input.  Resets option values from defaults
  305.  * established on command line.
  306.  */
  307. setoptions(s)
  308. char *s;
  309. {   int c, gap = -1;
  310.  
  311.     tex_opt = c_tex_opt;
  312.     utex_opt = c_utex_opt;
  313.     gap_opt = c_gap_opt;
  314.     black_opt = c_black_opt;
  315.     verbose_opt = c_verbose_opt;
  316.     quiet_opt = c_quiet_opt;
  317.     lexical_opt = c_lexical_opt;
  318.     T_opt = c_T_opt;
  319.     O_opt = c_O_opt;
  320.     I_opt = c_I_opt;
  321.     F_opt = c_F_opt;
  322.     E_opt = c_E_opt;
  323.     R_opt = c_R_opt;
  324.  
  325.     while (c = *s++)
  326.     switch (c) {
  327.         case 't': tex_opt = TRUE; utex_opt = FALSE; break;
  328.         case 'u': utex_opt = TRUE; tex_opt = TRUE; break;
  329.         case 'g': gap = gap_opt = atoi(s); break;
  330.         case 'b': black_opt = atoi(s); break;
  331.         case 'v': verbose_opt = TRUE; break;
  332.         case 'q': quiet_opt = TRUE; break;
  333.         case 'L': lexical_opt = TRUE; break;
  334.         case 'T': T_opt = TRUE; break;
  335.         case 'O': O_opt = TRUE; break;
  336.         case 'I': I_opt = TRUE; break;
  337.         case 'F': F_opt = TRUE; break;
  338.         case 'E': E_opt = TRUE; break;
  339.         case 'R': R_opt = TRUE; break;
  340.         case '\n': linenumber++; break;
  341.     }
  342.     if (gap >= 0 && tex_opt) gap_opt *= COLMUL;
  343. }
  344.  
  345.  
  346. extern char *optarg;        /* from getopt */
  347. extern int  optind;
  348.  
  349. main(argc, argv)
  350. int     argc;
  351. char   *argv[];
  352. {    int c;
  353.     char *progname = NULL, *basename();
  354.  
  355.     if ( (bufp = buf = (char *)malloc(NAMEROOM)) == 0 ) {
  356.         fprintf(stderr, "can't get memory space\n");
  357.         exit(1);
  358.     }
  359.  
  360.     progname = basename (argv[0]);
  361.     while ((c = getopt (argc, argv, "hg:tub:vLTOIFERdq")) != EOF)
  362.         switch (c) {
  363.             case 'g': c_gap_opt = max(0, atoi(optarg)); break;
  364.             case 't': c_tex_opt = TRUE; break;
  365.             case 'u': c_utex_opt = TRUE; c_tex_opt = TRUE; break;
  366.             case 'b': c_black_opt = max(0, atoi(optarg)); break;
  367.             case 'v': c_verbose_opt = TRUE; break;
  368.             case 'd': debug_opt = TRUE; break;
  369.             case 'q': c_quiet_opt = TRUE; break;
  370.             case 'L': c_lexical_opt = TRUE; break;
  371.             case 'T': c_T_opt = TRUE; break;
  372.             case 'O': c_O_opt = TRUE; break;
  373.             case 'I': c_I_opt = TRUE; break;
  374.             case 'F': c_F_opt = TRUE; break;
  375.             case 'E': c_E_opt = TRUE; break;
  376.             case 'R': c_R_opt = TRUE; break;
  377.             case 'h':
  378.                 default: 
  379.            fprintf(stderr, "Usage: %s [options] [files]\n", progname);
  380.            fprintf(stderr, "options = -gnum\t(gap between subtrees)\n");
  381.            fprintf(stderr, "          -h\t(print this information)\n");
  382.            fprintf(stderr, "          -t\t(TeX code)\n");
  383.            fprintf(stderr, "          -u\t(TeX code w. diagonals)\n");
  384.            fprintf(stderr, "          -bnum\t(black triangles)\n");
  385.            fprintf(stderr, "          -v\t(show TeX commands)\n");
  386.            fprintf(stderr, "          -q\t(quiet)\n");
  387.            fprintf(stderr, "          -L\t(lexical)\n");
  388.            fprintf(stderr, "          -T\t(triangles)\n");
  389.            fprintf(stderr, "          -O\t(omit lines)\n");
  390.            fprintf(stderr, "          -I\t(invert)\n");
  391.            fprintf(stderr, "          -F\t(flatten)\n");
  392.            fprintf(stderr, "          -E\t(even)\n");
  393.            fprintf(stderr, "          -R\t(relational)\n");
  394.            exit(1);
  395.         }
  396.  
  397.     /* doubled column values for tex code */
  398.     if (c_tex_opt) c_gap_opt *= COLMUL;
  399.  
  400.     BEGIN(N);
  401.  
  402.     if (optind >= argc) {
  403.         (void) yylex ();
  404.     }
  405.     else for (; (optind < argc); optind++) {
  406.         if (yyin == NULL) yyin = stdin;
  407.         if (freopen (argv[optind], "r", stdin) != NULL) {
  408. #ifdef FLEX_SCANNER    
  409.             /* to get flex to look at > 1 file */
  410.             yy_init = 1;
  411. #endif
  412.             (void) yylex ();
  413.             if (level) {
  414.                 fprintf(stderr,"Unbalanced parens in file: %s\n",
  415.                 argv[optind]);
  416.                 exit(1);
  417.             }
  418.         }
  419.         else {
  420.             (void) fprintf (stderr,
  421.                 "Couldn't open file: %s\n", argv[optind]);
  422.             exit (1);
  423.         }
  424.     }
  425.     if (level) {
  426.         fprintf(stderr,"Unbalanced parens.\n");
  427.         exit(1);
  428.     }
  429. }
  430.  
  431.  
  432. char   *basename (s)
  433. char   *s;
  434. {
  435.     char   *p, *strrchr();
  436.  
  437.     if (p = strrchr(s, '/'))
  438.         return(++p);
  439.     else return(s);
  440. }
  441.  
  442. max(a, b)
  443. int a, b;
  444. {
  445.     return ((a > b) ? a : b);
  446. }
  447.  
  448. TREE newnode(row, n)
  449. int  row;
  450. char *n;
  451. {    TREE temp;
  452.     int i;
  453.  
  454.     temp = (TREE) malloc (sizeof (LIST));
  455.     if (!temp) {
  456.         ERROR("out of memory");
  457.         exit(1);
  458.     }
  459.     temp->daughter = NULL;
  460.     temp->sister = NULL;
  461.     temp->mother = NULL;
  462.     temp->right = NULL;
  463.     temp->left = NULL;
  464.     temp->n = n;
  465.     temp->l = 0;
  466.     temp->row = row;
  467.     temp->col = 0;
  468.     temp->mid = 0;
  469.     temp->treeid = treenum++;
  470.     temp->type = NODENAME;
  471.     for (i = 0; i < 26; i++) temp->attrib[i] = '\0';
  472.     if (lexical_opt) give(temp,'L');
  473.     if (T_opt) give(temp,'T');
  474.     if (O_opt) give(temp,'O');
  475.     if (R_opt) give(temp,'R');
  476.     return (temp);
  477. }
  478.  
  479. /* append one node name character in buffer;  this is called only
  480.  * from within yylex().
  481.  */
  482. addchar(c)
  483. char c;
  484. {
  485.     *bufp++ = c;
  486. }
  487.  
  488. /* after yylex() has built an in-memory tree structure, printtee()
  489.  * formats and displays it.
  490.  */
  491. printtree(root)
  492. TREE root;
  493. {    TREE over;
  494.  
  495.     addbars(root, 0);            /* put in VBARs and HBARs         */
  496.     flatbars(root, maxlevel);        /* interpret \E and \F commands   */
  497.     rectify(root);                /* `left' links for row/col order */
  498.     addlinks(root);                /* miscellaneous initialization   */
  499.     over = newnode(0, NULL);        /* preliminary to calling align:  */
  500.     over->daughter = root;            /*    new node is needed for the  */
  501.     root->mother = root->left = over;   /*    case of an inverted root    */
  502.     if (I_opt) {
  503.     /* for side-by-side trees, interpret -I option as meaning that
  504.      * each tree should be inverted individually
  505.      */
  506.         if (root->l) give(root,'I');
  507.         else if (root->daughter) {
  508.         TREE node = root->daughter;
  509.         if (node->type == HBAR) node = node->daughter;
  510.         if (node->type == VBAR)
  511.             while (node && node->type == VBAR) {
  512.                 give(node->daughter,'I');
  513.                 node = node->sister;
  514.         }
  515.         else while (node) {
  516.                 give(node,'I');
  517.                 node = node->sister;
  518.         }
  519.         }
  520.     }
  521.     align(root);                /* assign column values for       */
  522.                         /*    vertical alignment          */
  523.     root = over->daughter;            /* root will be a different node  */
  524.                         /*    if it was just inverted     */
  525.     free(over);
  526.     if (debug_opt) {
  527.         fprintf(stderr,"\n\n\t------ROOT------\n");
  528.         debugprint(root);
  529.     }
  530.     if (!root->l) {                /* remove empty top nodes to get  */
  531.                         /*    side-by-side trees          */
  532.         TREE old;
  533.         if (root->daughter) {
  534.             old = root;
  535.             root = root->daughter;
  536.             free(old);
  537.         }
  538.         if (root->type == HBAR && root->daughter) {
  539.             TREE node;
  540.             old = root;
  541.             root = root->daughter;
  542.             free(old);
  543.         /* mothers of roots are made NULL to block the middle
  544.          * vertical of an HBAR for tty output
  545.          */
  546.             if (root->type == VBAR && root->daughter) {
  547.                 for (node = root; node; node = node->sister)
  548.                   if (node->daughter) node->daughter->mother = NULL;
  549.                 old = root;
  550.                 root = root->daughter;
  551.                 free(old);
  552.             }
  553.         }
  554.         else if (root->type == VBAR && root->daughter) {
  555.             old = root;
  556.             root = root->daughter;
  557.             free(old);
  558.         }
  559.         root->mother = NULL;
  560.     }
  561.     if (tex_opt) tex(root);    /* now display */
  562.     else tty(root);
  563.     bufp = buf;        /* can reuse name buffer for next tree */
  564.     freenodes(root);
  565. }
  566.  
  567. freenodes(tree)
  568. TREE tree;
  569. {    TREE next;
  570.  
  571.     while (tree) {
  572.         next = tree->right;
  573.         free(tree);
  574.         tree = next;
  575.     }
  576. }
  577.  
  578.  
  579. /* b is from the value given for the -b option */
  580. int b;
  581. /* these are the characters used to draw screen trees; the arrays
  582.  * are indexed by variable b above
  583.  */
  584. char tf[]    = "_-:|::|-|*";    /* triangle fill */
  585. char itf[]   = "~-:|::|-|*";    /* inverted triangle fill */
  586. char vb[]    = "||:|::||||";    /* vertical bar */
  587. char lhb[]   = "_-.|:._<//";    /* left part of horizontal bar */
  588. char rhb[]   = "_-.|:._>\\\\";    /* right part of horizontal bar */
  589. char ilhb[]  = "~-\"|:\"^<\\\\";/* left of inverted horizontal bar */
  590. char irhb[]  = "~-\"|:\"^>//";    /* right of inverted horizontal bar */
  591. char lvb[]   = "_-.|://<//";    /* left of vertical centerpiece */
  592. char mvb[]   = " +:|:     ";    /* middle of vertical centerpiece */
  593. char rvb[]   = "_+.|:\\\\>\\\\";/* right of vertical centerpiece */
  594. char lcb[]   = " |:|://///";    /* vertical for left sister */
  595. char rcb[]   = " |:|:\\\\\\\\\\";/* vertical for right sister */
  596. char lchb[]  = "_+ |:     ";    /* left corner of horizontal bar */
  597. char rchb[]  = "_+ |:     ";    /* right corner of horizontal bar */
  598. char ilchb[] = "_+ |:     ";    /* left corner of inv'd horizontal bar */
  599. char irchb[] = "_+ |:     ";    /* right corner of inv'd horizontal bar */
  600.  
  601.  
  602. /* display tree for screen */
  603. tty(root)
  604. TREE root;
  605. {    TREE node;
  606.     int row = root->row, col = 0, i;
  607.  
  608.     if (debug_opt) {
  609.         putchar('\n');
  610.         for (col = 0; col < indent; col++) putchar(' ');
  611.         col = 0;
  612.     }
  613.  
  614.     /* display each node, left-to-right and top-to-bottom */
  615.     for (node = root; node; node = node->right) {
  616.  
  617.         /* boldness is from \B command or -b option */
  618.         if (b = has(node,'B')) {
  619.             if (b == '+') b = 9;
  620.             else if (isdigit(b)) b -= '0';
  621.             else b = 0; /* presumably impossible */
  622.         }
  623.         else for (b = black_opt; b > 10; b /= 10) ;
  624.  
  625.         /* newline and indentation */
  626.         if (node->row > row) {
  627.             while (node->row > row) { putchar('\n'); row++; }
  628.             for (col = 0; col < indent; col++) putchar(' ');
  629.             col = 0;
  630.         }
  631.  
  632.         /* spacing between nodes */
  633.         for ( ; node->col > col; col++) putchar(' ');
  634.  
  635.         /* disconnect illegitimate sisters created by inversion */
  636.         if (node->sister && node->sister->mother != node->mother)
  637.             node->sister = NULL;
  638.  
  639.         /* display a node in a way appropriate to its type */
  640.         switch (node->type) {
  641.             case NODENAME:
  642.                 if (has(node,'P')) /* space over phantom node */
  643.                 for (i = 0; i < node->l; i++) putchar(' ');
  644.                 else printf("%s", node->n);
  645.                 break;
  646.             case VBAR:
  647.                 /* join all verticals at the base of a triangle */
  648.                 if (has(node,'T') && !has(node,'O')) {
  649.                 char hbar = tf[b];
  650.                 /* no vertical if this is not the first or
  651.                  * only sister
  652.                  */
  653.                 if (has(node,'S') != 'f'
  654.                      && has(node,'S') != 'o') {
  655.                     for (i = 0; i < node->l; i++)
  656.                         putchar(' ');
  657.                     break;
  658.                 }
  659.                 /* use special fill character for base of
  660.                  * inverted triangle
  661.                  */
  662.                 if (node->mother && node->mother->type == OBAR)
  663.                     hbar = itf[b];
  664.                 /* make left edge of base */
  665.                 putchar(vb[b]);
  666.                 /* when only one node at base, length of base
  667.                  * is length of node
  668.                  */
  669.                 if (has(node,'S') == 'o')
  670.                     for (i = 2; i < node->l; i++)
  671.                     putchar(hbar);
  672.                 /* but when there are several nodes at the
  673.                  * base, the base goes from the first to the
  674.                  * last sister
  675.                  */
  676.                 else {
  677.                     while (node->sister
  678.                       && node->mother == node->sister->mother
  679.                       && has(node,'S') != 'l'
  680.                       && node->sister->type == VBAR)
  681.                     node = node->sister;
  682.                     for ( ; node->col > col+1; col++)
  683.                     putchar(hbar);
  684.                     col++;
  685.                 }
  686.                 /* make the right edge of the base */
  687.                 putchar(vb[b]);
  688.                 break;
  689.                 } /* end of code for triangle bases */
  690.  
  691.                 /* space over omitted or phantom lines */
  692.                 if (has(node,'O') || has(node,'P')) putchar(' ');
  693.                 /* possibly do a bold vertical */
  694.                 else if (!blackvbar(node))
  695.                 /* do a plain vertical */
  696.                 putchar(vb[b]);
  697.                 break;
  698.  
  699.             case HBAR:
  700.                 /* possibly do a bold hbar */
  701.                 if (node->l >= 4 && blackhbar(node)) break;
  702.                 /* otherwise, make the left side, */
  703.                 for (i = 0; i < node->mid; i++) putchar(lhb[b]);
  704.                 /* ... then the middle */
  705.                 if (node->mother) putchar(vb[b]);
  706.                 else putchar(lhb[b]);
  707.                 /* ... then the right side */
  708.                 for (i = 0; i < node->l - node->mid - 1; i++)
  709.                 putchar(rhb[b]);
  710.                 break;
  711.  
  712.             case OBAR:
  713.                 /* similar to hbar, above */
  714.                 if (node->l >= 4 && blackobar(node)) break;
  715.                 for (i = 0; i < node->mid; i++) putchar(ilhb[b]);
  716.                 if (node->mother && node->right) putchar(vb[b]);
  717.                 else putchar(ilhb[b]);
  718.                 for (i = 0; i < node->l - node->mid - 1; i++)
  719.                 putchar(irhb[b]);
  720.                 break;
  721.         } /* end of switch */
  722.  
  723.         col += node->l;
  724.  
  725.     } /* end of loop to display each node */
  726. }
  727.  
  728.  
  729. /* draw horizontal bar with corners missing and a centerpiece */
  730. blackhbar(node)
  731. TREE node;
  732. {    int i, lless;
  733.  
  734.     /* don't do it if no boldness requested or a \Head has forced
  735.      * the "midpoint" of the hbar to one end
  736.      */
  737.     if (!b || !node->mid || node->mid +1 >= node->l) return(FALSE);
  738.  
  739.     /* make the center of the bar a little to the left, usually,
  740.      * for even-length bars, so the two parts of the centerpiece
  741.      * tend to come under the middle two characters of the name above
  742.      */
  743.     lless = (node->l % 2 && b < 8) ? 2 : 1;
  744.  
  745.     /* the left corner */
  746.     putchar(lchb[b]);
  747.  
  748.     /* the left segment before the centerpiece */
  749.     for (i = lless; i < node->mid; i++) putchar(lhb[b]);
  750.  
  751.     /* lower levels of bolding look better with a one-char
  752.      * centerpiece
  753.      */
  754.     if (b < 3) {
  755.         if (lless == 2) putchar(lhb[b]);
  756.         putchar(mvb[b]);
  757.         putchar(rhb[b]);
  758.     }
  759.     else {
  760.     /* the two-char centerpiece */
  761.         putchar(lvb[b]);
  762.         if (lless == 2) putchar(mvb[b]);
  763.         putchar(rvb[b]);
  764.     }
  765.  
  766.     /* now the right segment before the corner */
  767.     for (i = 3; i < node->l - node->mid; i++)
  768.         putchar(rhb[b]);
  769.  
  770.     /* finally the right corner */
  771.     putchar(rchb[b]);
  772.  
  773.     /* yes, we did one */
  774.     return(TRUE);
  775. }
  776.  
  777. /* as above, but for inverted trees */
  778. blackobar(node)
  779. TREE node;
  780. {    int i, lless;
  781.  
  782.     if (!b || !node->mid || node->mid +1 >= node->l) return(FALSE);
  783.  
  784.     lless = (node->l % 2 && b < 8) ? 2 : 1;
  785.     putchar(ilchb[b]);
  786.     for (i = lless; i < node->mid; i++) putchar(ilhb[b]);
  787.     if (b < 3) {
  788.         if (lless == 2) putchar(ilhb[b]);
  789.         putchar(mvb[b]);
  790.         putchar(irhb[b]);
  791.     }
  792.     else {
  793.         if (b == 7) putchar(lvb[b]);
  794.         else putchar(rvb[b]);
  795.         if (lless == 2) putchar(mvb[b]);
  796.         if (b == 7) putchar(rvb[b]);
  797.         else putchar(lvb[b]);
  798.     }
  799.     for (i = 3; i < node->l - node->mid; i++)
  800.         putchar(irhb[b]);
  801.     putchar(irchb[b]);
  802.     return(TRUE);
  803. }
  804.  
  805. /* draw corner sisters appropriate to horizontal above them */
  806. blackvbar(node)
  807. TREE node;
  808. {
  809.     /* don't do it when no boldness was asked for, or there is
  810.      * no node name above, or the hbar above was too short to
  811.      * be made bold
  812.      */
  813.     if (!b || !node->mother || node->mother->l < 4)
  814.         return(FALSE);
  815.     /* mark heads */
  816.     if (b >= 5 && has(node,'H')) {
  817.         putchar('*');
  818.         return(TRUE);
  819.     }
  820.     /* if it's the first sister, use a corner char */
  821.     if (has(node,'S') == 'f') {
  822.         if (node->mother->type == HBAR) {
  823.             putchar(lcb[b]);
  824.             return(TRUE);
  825.         }
  826.         if (node->mother->type == OBAR) {
  827.             putchar(rcb[b]);
  828.             return(TRUE);
  829.         }
  830.     }
  831.     /* likewise if its the last sister, but use the other corner char */
  832.     else if (has(node,'S') == 'l') {
  833.         if (node->mother->type == HBAR) {
  834.             putchar(rcb[b]);
  835.             return(TRUE);
  836.         }
  837.         if (node->mother->type == OBAR) {
  838.             putchar(lcb[b]);
  839.             return(TRUE);
  840.         }
  841.     }
  842.     return(FALSE);
  843. }
  844.  
  845. /* take care of spacing between daughters of a branching node, and
  846.  * figure width of the sisters; called by align()
  847.  */
  848. sisterbal(tree)
  849. TREE tree;
  850. {
  851.     TREE temp, first, last, head = NULL;
  852.     int hblen, rlen, bestspace, space, numdaughters = 1, leeway;
  853.     int join = FALSE;
  854.  
  855.     /* figure which sisters are to be covered by the bar; mark them
  856.      * for convenience later in display routines
  857.      */
  858.     for (first = tree->daughter; has(first,'O') && first->sister;
  859.          first = first->sister);
  860.     for (last = first; last->sister; last = last->sister);
  861.     while (has(last,'O') && last != first) last = last->left;
  862.     giveval(first,'S','f');
  863.     giveval(last,'S','l');
  864.  
  865.     /* look for heads and nodes that came from the bottom of inverted
  866.      * subtrees -- we must not try to balance the latter
  867.      */
  868.     for (temp = first; temp != last; temp = temp->sister) {
  869.         numdaughters++ ;
  870.         if (has(temp, 'H')) head = temp;
  871.         if (has(temp->sister, 'H')) head = temp->sister;
  872.         if (has(temp, 'I') == 2) join = TRUE;
  873.         if (has(temp->sister, 'I') == 2) join = TRUE;
  874.     }
  875.  
  876.     /* first approximation to the length of the bar */
  877.     hblen = (last->col + last->l) - first->col;
  878.     rlen = (last->col + last->mid + 1/*COLMUL*/) - (first->col + first->mid);
  879.  
  880.     /* first, try to adjust in a way that does not require
  881.      * widening the bar
  882.      */
  883.     if (numdaughters > 2) bestspace = rlen / (numdaughters - 1);
  884.     else bestspace = 0;
  885.     if (!join) for (temp = first; temp != last; temp = temp->sister) {
  886.         space = temp->sister->col + temp->sister->mid
  887.              - (temp->col + temp->mid);
  888.         leeway = rightroom(temp) - gap_opt;
  889.         if (temp == first && numdaughters == 2) leeway /= 2;
  890.         if (space > bestspace && leeway > 0) {
  891.             space -= bestspace;
  892.             if (space > leeway) space = leeway;
  893.             moveright(temp, space);
  894.             if (temp == first) {
  895.                 hblen = (last->col + last->l)
  896.                  - tree->daughter->col;
  897.                 rlen = (last->col + last->mid + 1/*COLMUL*/)
  898.                 - (first->col + first->mid);
  899.                 bestspace = rlen / (numdaughters - 1);
  900.             }
  901.         }
  902.     }
  903.     bestspace = 0;
  904.  
  905.     /* then look for the widest space between adjacent sisters, and
  906.      * widen the space between others to match
  907.      */
  908.     if (!join) for (temp = first; temp != last; temp = temp->sister) {
  909.         if ((space = temp->sister->col + temp->sister->mid
  910.             - (temp->col + temp->mid)) > bestspace)
  911.             bestspace = space;
  912.     }
  913.     if (!join) for (temp = first; temp != last; temp = temp->sister) {
  914.         if ((space = temp->sister->col + temp->sister->mid
  915.             - (temp->col + temp->mid)) < bestspace)
  916.             moveright(temp->sister, bestspace - space);
  917.     }
  918.  
  919.     /* triangles with a single node at their bases are a special case */
  920.     if (last == first && last->daughter) {
  921.         hblen = last->daughter->l;
  922.         last->l = last->daughter->l;
  923.         last->col = last->daughter->col;
  924.         giveval(last,'S','o');
  925.     }
  926.     /* revise hbar length and fill in lengths */
  927.     else hblen = (last->col + last->l) - first->col;
  928.     tree->l = hblen;
  929.     if (head) tree->mid = head->col + head->mid - first->col;
  930.     else tree->mid = (hblen - 1) / 2;
  931. /* ( arguably, when slanty lines will be drawn, the length of the
  932.  * hbar should be a little less -- must try this some day )
  933.  */
  934.  
  935.     /* if the left edge of the hbar is to the right of the left
  936.      * edge of the first sister, align all the sisters now
  937.      */
  938.     if ((space = tree->col - first->col) > 0) {
  939.         for (temp = tree->daughter; temp; temp = temp->sister)
  940.             moveright(temp, space);
  941.         return(0);
  942.     }
  943.     /* otherwise, tell align() to move the hbar to the right */
  944.     return(space);
  945. }
  946.  
  947. /* assign col values to nodes for appropriate vertical alignments;
  948.  * also call for inversion of trees with \Is
  949.  */
  950. align(tree)
  951. TREE tree;
  952. {    int diff, thisrow;
  953.     TREE offspring, invert();
  954.  
  955.     if (tree) {
  956.     /* the vbar of a relational node has already been aligned */
  957.     if (has(tree,'R') && tree->type == VBAR) return;
  958.  
  959.     /* every node has to go at least far enough to the right to
  960.      * avoid bumping into the node on the left (if any)
  961.      */
  962.     if (tree->left && tree->left->row == tree->row)
  963.         tree->col = tree->left->col + tree->left->l + gap_opt;
  964.     else tree->col = 0;
  965.  
  966.     /* force relational nodes to align on the vbar, by artifically
  967.      * considering the vbar to be at the "midpoint" of the node
  968.      */
  969.     if (has(tree,'R') && tree->type == NODENAME && tree->sister) {
  970.         tree->sister->col = tree->col + tree->l + gap_opt/4;
  971.         tree->mid = tree->sister->col + tree->sister->mid - tree->col;
  972.     }
  973.  
  974.     /* for non-terminal nodes, align the lower parts of the tree
  975.      * (cyclically), and calculate the displacement required to
  976.      * line this tree up above its offspring
  977.      */
  978.         if (offspring = tree->daughter) {
  979.         align(offspring);
  980.         offspring = tree->daughter; /* may have different tree if inverted*/
  981.         diff = 0;
  982.         if (tree->type == HBAR) {
  983.         /* do not change alignment of the top (formerly bottom)
  984.          * parts of an inverted subtree, since they are already
  985.          * properly aligned with nodes below them; but the whole
  986.          * subtree can be moved by its top left node
  987.          */
  988.         if (has(tree,'I') == 1) diff = tree->col - offspring->col;
  989.         else diff = sisterbal(tree);
  990.         }
  991.         /* the case of sisters which are not under an hbar can arise
  992.          * through use of \L; we center the tree over them
  993.          */
  994.         else if (has(offspring,'I') != 2 && has(offspring,'I') != 3
  995.              && offspring->sister && !has(offspring->sister,'R')) {
  996.         TREE temp, first, last;
  997.         for (first = offspring; has(first,'O') && first->sister;
  998.              first = first->sister);
  999.         for (last = first; last->sister; last = last->sister);
  1000.         if (last == first) first = offspring;
  1001.         else while (has(last,'O') && last != first) last = last->left;
  1002.         for (temp = first; ; temp = temp->sister) {
  1003.             if (has(temp,'H')) first = last = temp;
  1004.             if (temp == last) break;
  1005.         }
  1006.         diff = tree->col + tree->mid
  1007.             - (first->col + first->mid
  1008.                + last->col + last->mid)/2;
  1009.         }
  1010.         /* here the tree has a single daughter; line up the midpoints */
  1011.         else {
  1012.         /* this propagates a mark up the tree that tells the
  1013.          * sisterbal() routine not to change the alignment of
  1014.          * an empty node that has been attached to part of an
  1015.          * inverted tree, because that would undo the work we
  1016.          * did in attaching it
  1017.          */
  1018.         if (has(offspring,'I') == 2) giveval(tree,'I',2);
  1019.         diff = tree->col + tree->mid
  1020.             - (offspring->col + offspring->mid);
  1021.         }
  1022.  
  1023.         /* now actually do the alignment by moving either the tree
  1024.          * or the offspring to the right, whichever is required
  1025.          */
  1026.         if (diff > 0) {
  1027.         moveright(offspring, diff);
  1028.         /* move the bar at the right of a relational node along
  1029.          * with the node
  1030.          */
  1031.         if (has(offspring->sister,'R')
  1032.             && offspring->sister->type == VBAR)
  1033.             offspring->sister->col += diff;
  1034.         /* this is a duplication of effort, I think, but it does
  1035.          * have to be done here
  1036.          */
  1037.         else align(offspring->sister);
  1038.         }
  1039.         else if (diff < 0) {
  1040.         tree->col -= diff;
  1041.         if (has(tree->sister,'R')) tree->sister->col -= diff;
  1042.         }
  1043.     }
  1044.  
  1045.     /* in the case of a terminal node, there is ordinarily nothing
  1046.      * to do, but it may be possible to align empty nodes with parts of
  1047.      * an inverted subtree beneath them
  1048.      */
  1049.     else if (tree->type == VBAR) { /* a terminal vbar is an "empty node" */
  1050.     /* An inverted subtree is connected to the rest by its upper left
  1051.      * corner, which as been conveniently marked with an I-attribute
  1052.      * value of 3.  We are going work our way to the left along the
  1053.      * current row looking for such a corner, then if we find one,
  1054.      * go down one row to the top row of the inverted subtree and
  1055.      * work our way right an equal number of nodes to find a node to
  1056.      * align with.  After the corner, nodes in this top row have been
  1057.      * marked with an I-attribute value of 2, so we can tell when
  1058.      * the search has failed.
  1059.      */
  1060.         TREE node = tree, invh = NULL;
  1061.         int bcount = 1;
  1062.         /* first work our way left: */
  1063.         while (node->left && node->left->row == node->row) {
  1064.         if (debug_opt)
  1065.             printf("\nAL: at #%d going left to #%d.",
  1066.             node->treeid,node->left->treeid);
  1067.         if (has(node->left->daughter,'I') == 3) {
  1068.             invh = node->left->daughter;
  1069.             break;
  1070.         }
  1071.         else {
  1072.             node = node->left;
  1073.             bcount++;
  1074.         }
  1075.         }
  1076.         /* then right an equal distance along top of inverted tree */
  1077.         while (bcount && invh && has(invh->sister,'I') == 2) {
  1078.         if (debug_opt)
  1079.             printf("\nAL: at #%d going right to #%d.",
  1080.             invh->treeid,invh->sister->treeid);
  1081.         invh = invh->sister;
  1082.         bcount--;
  1083.         }
  1084.         /* have we found one? yes, if we're still in the inverted
  1085.          * tree and the node is not to the left of us (we can't
  1086.          * move this tree node to the left -- only to the right)
  1087.          */
  1088.         if (has(invh,'I') == 2 && tree->col + tree->mid <= invh->col + invh->mid) {
  1089.         if (debug_opt)
  1090.             printf("\naligning #%d over #%d.\n",
  1091.             tree->treeid,invh->treeid);
  1092.         /* do the alignment */
  1093.         tree->col = invh->col + invh->mid - tree->mid;
  1094.         /* mark as not subject to balancing by sisterbal() */
  1095.         giveval(tree,'I',2);
  1096.         }
  1097.     } /* end alignment of terminal node */
  1098.  
  1099.     /* if inversion was requested, do it */
  1100.     if (has(tree,'I') == '+')
  1101.         tree = invert(tree);
  1102.  
  1103.     /* recurse left-to-right */
  1104.     align(tree->sister);
  1105.     }
  1106. }
  1107.  
  1108. /* do inversion of a tree; much global info in the tree has to be
  1109.  * kept correct, so this is hard;  the actual inversion is done
  1110.  * by inv(); invert() is called by align() just above
  1111.  */
  1112. TREE invert(tree)
  1113. TREE tree;
  1114. {    TREE mother, sister, node, inv();
  1115.  
  1116.     /* make all nodes in each row sisters; makes inversion easier,
  1117.      * and makes it possible later to move the inverted tree around from
  1118.      * above
  1119.      */
  1120.     makelbranch(tree);
  1121.     /* save these links for later reattachment */
  1122.     mother = tree->mother;
  1123.     sister = tree->sister;
  1124.     tree->sister = NULL;
  1125.     tree = inv(tree, NULL);
  1126.     /* in the special case where a tree has VBARs at the top
  1127.      * after inversion, put an HBAR over the VBARs
  1128.      */
  1129.     if (tree->sister && mother && mother->type == VBAR
  1130.         && tree->type == VBAR && tree->sister->type == VBAR
  1131.         && (!mother->mother || mother->mother->type != HBAR)) {
  1132.             TREE last;
  1133.             for (last = tree->sister;
  1134.                 last->sister && last->sister->type == VBAR;
  1135.                 last = last->sister)
  1136.                  last->mother = mother;
  1137.             last->mother = mother;
  1138.             mother->type = HBAR;
  1139.             giveval(mother,'I',1);
  1140.             mother->l = last->col + last->l - tree->col;
  1141.             mother->mid = (mother->l - 1)/2;
  1142.     }
  1143.     /* otherwise mark the top row so align() can tell that these
  1144.      * nodes are at the top of an inverted tree and can find the
  1145.      * top left corner
  1146.      */
  1147.     else if (mother && !(mother->type == VBAR && has(mother,'O'))) {
  1148.         for (node = tree; node; node = node->sister)
  1149.             giveval(node,'I',2);
  1150.         giveval(tree,'I',3);
  1151.     }
  1152.     /* it's possible that inversion has caused parts of the inverted
  1153.      * tree to bump against things to the left;  now check for this
  1154.      * and, to preserve internal alignment, when necessary move the
  1155.      * entire subtree to the right
  1156.      */
  1157.     for (node = tree; node; node = node->daughter) {
  1158.         TREE temp;
  1159.         int room;
  1160.         if (node->left && node->left->row == node->row)
  1161.         if ((room = node->left->col + node->left->l + gap_opt
  1162.                         - node->col) > 0)
  1163.             for (temp = tree; temp; temp = temp->sister)
  1164.             moveright(temp, room);
  1165.     }
  1166.     /* if this corner of the tree is a vbar, should a line be drawn
  1167.      * to an hbar above, or an obar below?  maybe both -- I really
  1168.      * don't know
  1169.      */
  1170.     tree->mother = mother; /* ?? */
  1171.  
  1172.     /* in -L trees, following not quite right */
  1173.     if (mother) {
  1174.         mother->daughter = tree;
  1175.     }
  1176.     /* reattach former sister to rightmost sister of top */
  1177.     while (tree->sister) tree = tree->sister;
  1178.     tree->sister = sister;
  1179.  
  1180.     return(tree);
  1181. }
  1182.  
  1183. /* see how much a tree could be moved to the right without coming
  1184.  * too close to anything following; called by sisterbal()
  1185.  */
  1186. rightroom(west)
  1187. TREE west;
  1188. {    int mingap = 10000, gap;
  1189.     TREE node, south = NULL;
  1190.  
  1191.     if (west) south = west->daughter;
  1192.     else return(0);
  1193.     while (west) {
  1194.         if (west->right && west->row == west->right->row) {
  1195.             gap = west->right->col - west->col - west->l;
  1196.             if (gap < mingap) mingap = gap;
  1197.         }
  1198.         node = south;
  1199.         south = west = NULL;
  1200.         while (node) {
  1201.             west = node;
  1202.             if (node->daughter) south = node->daughter;
  1203.             node = node->sister;
  1204.         }
  1205.     }
  1206.     return(mingap);
  1207. }
  1208.  
  1209. /* move a tree right by increasing col values */
  1210. moveright(tree, amount)
  1211. TREE tree;
  1212. int amount;
  1213. {
  1214.     while (tree) {
  1215.         tree->col += amount;
  1216.         if (tree = tree->daughter) {
  1217.             TREE sis;
  1218.             sis = tree->sister;
  1219.             while (sis) {
  1220.                 moveright(sis, amount);
  1221.                 sis = sis->sister;
  1222.             }
  1223.         }
  1224.     }
  1225. }
  1226.  
  1227. /* flip a tree organized as a stack of linked sets of sisters, keeping
  1228.  * left and right links correct; gah!; called by invert()
  1229.  */
  1230. TREE inv(tree,rest)
  1231. TREE tree, rest;
  1232. {    TREE temp, node, right, left, last, lastd;
  1233.     int row;
  1234.  
  1235.     if (tree) {
  1236.         temp = tree->daughter;
  1237.         tree->daughter = rest;
  1238.  
  1239.         for (node = tree; node; node = node->sister) {
  1240.             if (node->type == HBAR) node->type = OBAR;
  1241.             else if (node->type == OBAR) node->type = HBAR;
  1242.             else if (node->type == VBAR) {
  1243.             /* this is so texvbar() can tell when to invert
  1244.              * arrows when bold verticals have been requested
  1245.              */
  1246.             if (has(node,'U') == 'i') giveval(node,'U','u');
  1247.             else giveval(node,'U','i');
  1248.             }
  1249.         }
  1250.  
  1251.         row = tree->row;
  1252.         for (last = tree; last->sister; last = last->sister) ;
  1253.         right = last->right;
  1254.         left = tree->left;
  1255.         node = tree;
  1256.         while (node && node->daughter) {
  1257.             for (last = node; ;) {
  1258.                 last->row = node->daughter->row;
  1259.                 if (!last->sister) break;
  1260.                 last = last->sister;
  1261.             }
  1262.             for (lastd = node->daughter; lastd->sister;
  1263.                 lastd = lastd->sister) ;
  1264.             if (lastd->right) last->right = lastd->right;
  1265.             else last->right = node->daughter;
  1266.             if (node->daughter->left)
  1267.                 node->left = node->daughter->left;
  1268.             last->right->left = last;
  1269.             if (node->left) node->left->right = node;
  1270.             node = node->daughter;
  1271.         }
  1272.         if (left) node->left = left;
  1273.         else node->left = last;
  1274.         for (last = node; ;) {
  1275.             last->row = row;
  1276.             if (!last->sister) break;
  1277.             last = last->sister;
  1278.         }
  1279.         last->right = right;
  1280.         if (right) right->left = last;
  1281.         if (left) left->right = node;
  1282.  
  1283.         if (debug_opt) { fprintf(stderr,"\n\nCalled inv():\n");
  1284.                  debugprint(tree); }
  1285.         return(inv(temp,tree));
  1286.     }
  1287.     else return(rest);
  1288. }
  1289.  
  1290. /* convert a tree to left-branching; this is a preliminary to inverting a tree;
  1291.  * called by invert()
  1292.  */
  1293. makelbranch(tree)
  1294. TREE tree;
  1295. {    TREE node, east, west, south, last;
  1296.  
  1297.     east = west = tree;
  1298.     while (tree) {
  1299.         for (node = east, last = south = NULL; ; node = node->right) {
  1300.             if (node->daughter) {
  1301.                 last = node->daughter;
  1302.                 if (!south) south = node->daughter;
  1303.                 node->daughter = NULL;
  1304.             }
  1305.             if (node == west) break;
  1306.             else node->sister = node->right;
  1307.         }
  1308.         if (west->right == south) west->right = NULL;
  1309.         if (south && south->left == west) south->left = NULL;
  1310.         while (last && last->sister) last = last->sister;
  1311.         west = last;
  1312.         east->daughter = south;
  1313.         tree = east = south;
  1314.     }
  1315. }
  1316.  
  1317. /* initialize some links to contiguous nodes, and also lengths and
  1318.  * mid column values
  1319.  */
  1320. addlinks(tree)
  1321. TREE tree;
  1322. {
  1323.     while (tree) {
  1324.         if (tex_opt) tree->l *= COLMUL;
  1325.         tree->mid = (tree->l - 1) / 2;
  1326.         if (tree->right) tree->right->left = tree;
  1327.         if (tree->daughter) tree->daughter->mother = tree;
  1328.         if (tree->sister) tree->sister->mother = tree->mother;
  1329.         tree = tree->right;
  1330.     }
  1331. }
  1332.  
  1333. /* for debugging */
  1334. printnode(node)
  1335. TREE node;
  1336. {    int i;
  1337.  
  1338.     if (!node) {
  1339.         fprintf(stderr,"NIL");
  1340.         return;
  1341.     }
  1342.     if (node->type == VBAR)
  1343.         fprintf(stderr,"#%d | at %d/%d", node->treeid,
  1344.             node->col, node->row);
  1345.     else if (node->type == HBAR)
  1346.         fprintf(stderr,"#%d _|_ at %d/%d", node->treeid,
  1347.             node->col, node->row);
  1348.     else if (node->type == OBAR)
  1349.         fprintf(stderr,"#%d ^|^ at %d/%d", node->treeid,
  1350.             node->col, node->row);
  1351.     else fprintf(stderr,"#%d=%s at %d/%d", node->treeid, node->n,
  1352.             node->col, node->row);
  1353.     fprintf(stderr,"[");
  1354.     for (i = 0; i < 26; i++) {
  1355.         char c;
  1356.         if ((c = node->attrib[i]) == '+')
  1357.             fprintf(stderr,"%c", 'A'+i);
  1358.         else if (c)
  1359.             fprintf(stderr,"%c=%d", 'A'+i, c);
  1360.     }
  1361.     fprintf(stderr,"]");
  1362. }
  1363.  
  1364. /* for debugging */
  1365. debugprint(tree)
  1366. TREE tree;
  1367. {
  1368.     if (tree) {
  1369.         debugprint(tree->daughter);
  1370.         printnode(tree);
  1371.         if (tree->daughter) {
  1372.             fprintf(stderr," DAUGHTER:");
  1373.             printnode(tree->daughter);
  1374.         }
  1375.         if (tree->sister) {
  1376.             fprintf(stderr," SISTER:");
  1377.             printnode(tree->sister);
  1378.         }
  1379.         fprintf(stderr,"\n  ");
  1380.         if (tree->mother) {
  1381.             fprintf(stderr," MOM:");
  1382.             printnode(tree->mother);
  1383.         }
  1384.         if (tree->left) {
  1385.             fprintf(stderr," LEFT:");
  1386.             printnode(tree->left);
  1387.         }
  1388.         if (tree->right) {
  1389.             fprintf(stderr," RIGHT:");
  1390.             printnode(tree->right);
  1391.         }
  1392.         fprintf(stderr,"\n");
  1393.         debugprint(tree->sister);
  1394.     }
  1395. }
  1396.  
  1397. /* create new VBAR or HBAR node; called by addbars() */
  1398. TREE newbar(model, row, bartype)
  1399. TREE model;
  1400. int row, bartype;
  1401. {    TREE temp;
  1402.     int i;
  1403.  
  1404.     temp = newnode(row, NULL);
  1405.     temp->type = bartype;
  1406.     temp->l = 1;
  1407.     for (i = 0; i < 26; i++) temp->attrib[i] = model->attrib[i];
  1408.  
  1409.     /* bars get the following attributes only when above empty
  1410.      * nodes (and that is done in addbars() when a NODENAME is
  1411.      * removed)
  1412.      */
  1413.     giveval(temp,'F',0);
  1414.     giveval(temp,'I',0);
  1415.     giveval(temp,'R',0);
  1416.  
  1417.     return(temp);
  1418. }
  1419.  
  1420. /* test node for value of attribute */
  1421. has(tree, attrib)
  1422. TREE tree;
  1423. char attrib;
  1424. {
  1425.     if (tree && attrib >= 'A' && attrib <= 'Z')
  1426.         return(tree->attrib[attrib - 'A']);
  1427.     else return(0);
  1428. }
  1429.  
  1430. /* give value of attribute to node */
  1431. giveval(tree, attrib, val)
  1432. TREE tree;
  1433. char attrib, val;
  1434. {    int prev;
  1435.  
  1436.     if (tree && attrib >= 'A' && attrib <= 'Z') {
  1437.         prev = tree->attrib[attrib - 'A'];
  1438.         tree->attrib[attrib - 'A'] = val;
  1439.         return(prev);
  1440.     }
  1441.     else return(0);
  1442. }
  1443.  
  1444. /* give `+' value of attribute to node */
  1445. give(tree, attrib)
  1446. TREE tree;
  1447. char attrib;
  1448. {
  1449.     return(giveval(tree, attrib, '+'));
  1450. }
  1451.  
  1452. /* stick in VBARs above name nodes, and HBARs under branching nodes;
  1453.  * also remove empty name nodes
  1454.  */
  1455. addbars(tree, addrows)
  1456. TREE tree;
  1457. int addrows;
  1458. {    TREE kin, mother, node, temp;
  1459.     int numsisters;
  1460.  
  1461.     if (tree) {
  1462.         /* account for new rows created above by adding bars */
  1463.         tree->row += addrows;
  1464.         /* I don't think maxlevel is used now, but may as well
  1465.          * keep it up to date
  1466.          */
  1467.         if (tree->row > maxlevel) maxlevel = tree->row;
  1468.         /* add no bars directly under node with \L */
  1469.         if (has(tree,'L')) {
  1470.             /* for -F option, propagate F attribute up from a
  1471.              * terminal to dominating \L nodes
  1472.              */
  1473.             if (F_opt && tree->daughter
  1474.              && !has(tree->daughter->daughter,'F')) {
  1475.             give(tree,'F'); /* work up through higher \L nodes */
  1476.             giveval(tree->daughter,'F',0);
  1477.             }
  1478.             /* save reference for following business with R nodes */
  1479.             node = tree;
  1480.             /* go down and add bars to lower parts of tree */
  1481.             tree = tree->daughter;
  1482.             while (tree) {
  1483.             addbars(tree, addrows);
  1484.             tree = tree->sister;
  1485.             }
  1486.             /* for -R, propagate absence of R attribute up from
  1487.              * terminals to dominating \L nodes
  1488.              */
  1489.             if (R_opt && !has(node->daughter,'R'))
  1490.             giveval(node,'R',0);
  1491.         }
  1492.         /* no \L command, so unless this is a terminal, we do want to
  1493.          * add bars under it -- either just a vbar, or for branching
  1494.          * nodes, an hbar and under that a vbar for each sister
  1495.          */
  1496.         else if (tree->daughter) {
  1497.         kin = mother = tree;
  1498.         tree = tree->daughter;
  1499.         /* nodes with \O will not be covered by an hbar, so count
  1500.          * the sisters that will be covered, to decide whether
  1501.          * this should appear as a branching node
  1502.          */
  1503.         for (node = tree, numsisters = 0; node; node = node->sister)
  1504.             if (!has(node,'O')) numsisters++;
  1505.         /* for tty output, a triangle base needs 3 characters,
  1506.          * and for triangles over single daughter nodes, the name
  1507.          * may be too short
  1508.          */
  1509.         if (!tex_opt && numsisters < 2 && tree->l < 3)
  1510.             giveval(kin,'T',0);
  1511.         /* triangles over single daughters do need an hbar, but
  1512.          * otherwise unless there are at least 2 sisters to cover,
  1513.          * no hbar is needed
  1514.          */
  1515.         if (numsisters > 1 || (has(kin,'T')
  1516.                 /* need at least one node at base */
  1517.                     && numsisters
  1518.                 /* a vbar cannot serve as a good base */
  1519.                     && tree->l
  1520.                 /* would get odd results over inverted tree */
  1521.                     && !has(tree,'I')
  1522.                       )
  1523.            ) {
  1524.             /* auto-evening for all branching nodes */
  1525.             if (E_opt) give(kin,'E');
  1526.             /* make the hbar and attach it */
  1527.             temp = newbar(kin, tree->row + addrows, HBAR);
  1528.             temp->mother = mother;
  1529.             mother = temp;
  1530.             temp->daughter = tree;
  1531.             kin->daughter = temp;
  1532.             /* shift lower parts of tree down one row */
  1533.             addrows++;
  1534.             kin = temp;
  1535.         }
  1536.         /* now add a vbar above the daughter and each sister */
  1537.         while (tree) {
  1538.             temp = newbar(tree, tree->row + addrows, VBAR);
  1539.             /* whether a vbar is part of a triangle is determined
  1540.              * by node above, not the one below it, and similarly
  1541.              * for bolding and \M labels
  1542.              */
  1543.             giveval(temp,'T',0);
  1544.             giveval(temp,'B',has(mother,'B'));
  1545.             giveval(temp,'M',0);
  1546.             if (mother->type == NODENAME)
  1547.             giveval(temp,'M',has(mother,'M'));
  1548.             if (has(mother,'T') && mother->type == HBAR && !has(temp,'O')) give(temp,'T');
  1549.  
  1550.             /* attach the new bar */
  1551.             temp->mother = mother;
  1552.             if (tree == kin->daughter) kin->daughter = temp;
  1553.             else kin->sister = temp;
  1554.             /* finish attachment and work down the tree if this
  1555.              * is a non-empty node
  1556.              */
  1557.             if (tree->l) {
  1558.             temp->daughter = tree;
  1559.             tree->mother = temp;
  1560.             addbars(tree, addrows+1);
  1561.             }
  1562.             /* but if it is an empty node, discard it after copying
  1563.              * attributes that we wouldn't want to lose
  1564.              */
  1565.             else {
  1566.             addbars(tree, addrows);
  1567.             temp->daughter = tree->daughter;
  1568.             if (tree->daughter) tree->daughter->mother = temp;
  1569.             if (has(tree,'F')) give(temp,'F');
  1570.             if (has(tree,'I')) give(temp,'I');
  1571.                 giveval(temp,'M',has(tree,'M'));
  1572.             free(tree);
  1573.             }
  1574.             /* make the single-noded base of a triangle wide enough
  1575.              * to cover the name below it, and cause the apex of
  1576.              * such a triangle to be moved downward together with
  1577.              * its base in case there is flattening
  1578.              */
  1579.             if (has(temp,'T') && numsisters == 1) {
  1580.             temp->l = tree->l;
  1581.             if (has(tree,'F')) {
  1582.                 give(kin,'F');
  1583.                 giveval(tree,'F',0);
  1584.             }
  1585.             }
  1586.             /* vbar takes over any link to sister at right */
  1587.             kin = temp;
  1588.             temp = tree->sister;
  1589.             tree->sister = NULL;
  1590.  
  1591.             /* add vertical to the right of relational node */
  1592.             if (has(tree,'R') && tree->type == NODENAME && tree->l
  1593.             && (!has(tree,'L') || has(tree->daughter,'R'))) {
  1594.                 TREE rtemp;
  1595.                     rtemp = newbar(tree, tree->row, VBAR);
  1596.                 give(rtemp,'R');
  1597.                 giveval(rtemp,'T',0);
  1598.                 giveval(rtemp,'O',0);
  1599.                 tree->sister = rtemp;
  1600.             }
  1601.             /* now loop to add vbar to sister, if any */
  1602.             tree = temp;
  1603.         }
  1604.         }
  1605.         /* here it's a terminal node; do flatten it if -F option,
  1606.          * but don't automatically display it as relational for -R opt.
  1607.          */
  1608.         else {
  1609.         if (F_opt) give(tree,'F');
  1610.         if (R_opt) giveval(tree,'R',0);
  1611.         }
  1612.     } /* if (tree) */
  1613. }
  1614.  
  1615. /* find lowest node in tree, ignoring inverted subtrees */
  1616. howlow(tree)
  1617. TREE tree;
  1618. {    int row, low = 0;
  1619.  
  1620.     while (tree) {
  1621.         if (tree->row > low) low = tree->row;
  1622.         tree = tree->daughter;
  1623.         if (tree && (row = howlow(tree->sister)) > low) low = row;
  1624.         if (tree && tree->type == NODENAME && has(tree,'I')) break;
  1625.     }
  1626.     return(low);
  1627. }
  1628.  
  1629. /* increase row numbers */
  1630. movedown(tree, amount)
  1631. TREE tree;
  1632. int amount;
  1633. {
  1634.     while (tree) {
  1635.         tree->row += amount;
  1636.         movedown(tree->sister, amount);
  1637.         tree = tree->daughter;
  1638.     }
  1639. }
  1640.  
  1641. /* add VBARs to bring \F'd constituents downward */
  1642. flatbars(tree, bottom)
  1643. TREE tree;
  1644. int bottom;
  1645. {    TREE node, temp, next;
  1646.     int far = bottom;
  1647.  
  1648.     if (tree) {
  1649.         if ( (tree->type == NODENAME || (tree->type == HBAR
  1650.              && tree->mother && tree->mother->type == VBAR) )
  1651.          && has(tree,'E') )
  1652.             bottom = howlow(tree);
  1653.         if (!(node = tree->daughter)) {
  1654.         temp = tree->left;
  1655.         if (temp && temp->sister == tree) {
  1656.             node = tree;
  1657.             tree = temp;
  1658.         }
  1659.         }
  1660.         while (node) {
  1661.         next = node->sister;
  1662.         if (next) next->left = node;
  1663.         if (node->daughter) {
  1664.             if (has(node,'F')) far -= howlow(node) - node->row;
  1665.             else flatbars(node, bottom);
  1666.         }
  1667.         if (has(node,'F')) {
  1668.             if (node->type == VBAR) far--;
  1669.             while (node->row < far) {
  1670.             temp = newbar(node, node->row, VBAR);
  1671.             temp->daughter = node;
  1672.             if (has(node,'R') && node->sister) node->sister->row++;
  1673.             else {
  1674.                 temp->sister = node->sister;
  1675.                 node->sister = NULL;
  1676.             }
  1677.             node->row++;
  1678.             if (node == tree->sister && next) next->left = temp;
  1679.             if (node == tree->daughter) tree->daughter = temp;
  1680.             else if (node == tree->sister) tree->sister = temp;
  1681.             /*else ERROR("flatbars");*/
  1682.             if (!tree->sister) giveval(tree,'T',0);
  1683.             if (node->type == VBAR && has(node,'T'))
  1684.                 giveval(node,'T',0);
  1685.             else giveval(temp,'T',0);
  1686.             node->mother = temp; /* ?? */
  1687.             tree = temp;
  1688.             }
  1689.             if (node->daughter) {
  1690.             movedown(node->daughter, node->row + 1
  1691.                 - node->daughter->row);
  1692.             }
  1693.         } /* end if (has(node,'F')) */
  1694.         tree = node;
  1695.         node = next;
  1696.         } /* end if (node) */
  1697.     } /* end if (tree) */
  1698. }
  1699.  
  1700. /* initialize `left' links in one row of tree; called by rectify() */
  1701. TREE rectifyrow(prev, root, row)
  1702. TREE prev, root;
  1703. int row;
  1704. {    TREE node = root, last = NULL, temp;
  1705.  
  1706.     if (node && node->row <= row) {
  1707.         if (node->row == row) {
  1708.             prev->right = node;
  1709.             if (debug_opt) {
  1710.                 fprintf(stderr,"\nLINK OF ");
  1711.                 printnode(prev);
  1712.                 fprintf(stderr," TO ");
  1713.                 printnode(node);
  1714.             }
  1715.             last = prev = node;
  1716.         }
  1717.         else if (temp = rectifyrow(prev, node->daughter, row))
  1718.             last = prev = temp;
  1719.         if (temp = rectifyrow(prev, node->sister, row))
  1720.             last = prev = temp;
  1721.     }
  1722.     return(last);
  1723. }
  1724.  
  1725. /* initialize `left' links so can traverse tree in row-column order */
  1726. rectify(root)
  1727. TREE root;
  1728. {    TREE node = root;
  1729.     int row;
  1730.  
  1731.     for (row = 2; node = rectifyrow(node, root, row); row++) ;
  1732. }
  1733.  
  1734. /* all TeX code in is tex.c */
  1735. #include "tex.c"
  1736.